package problem767;

//767.重构字符串
//https://leetcode.cn/problems/reorganize-string/

import java.util.HashMap;

class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        HashMap<Character, Integer> map = new HashMap<>();
        char k = ' ';
        int maxCount = 0;
        for(char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
            if(map.get(ch) > maxCount) {
                maxCount = map.get(ch);
                k = ch;
            }
        }
        if(maxCount > (n+1)/2) return "";
        char[] arr = new char[n];
        int index = 0;
        for(int i = 0; i<maxCount; i++) {
            arr[index] = k;
            index += 2;
        }
        map.remove(k);
        for(char x : map.keySet()) {
            for(int i = 0; i<map.get(x); i++) {
                if(index >= n) index = 1;
                arr[index] = x;
                index += 2;
            }
        }
        return new String(arr);
    }
}